package day_7_6;

public class Main2 {
    /**
     * 543. 二叉树的直径
     * https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int ret;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        // ret中的到的是最长的节点额的个数
        // 对于求取边来说，是需要再节点的个数上进行减一操作，才是最后的边的最大长度
        // 将整体进行减一，即为直径
        return ret - 1;
    }

    // 得到root的左右子树的最长的长度 + root本身，就是整个根节点的长度
    public int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = dfs(root.left);
        int right = dfs(root.right);
        ret = Math.max(ret,left + right + 1);
        return Math.max(left,right) + 1;
    }
}
